/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList
{
public:
    bool chkPalindrome(ListNode* A)
    {
        ListNode* fast, * slow;
        fast = slow = A;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* n2 = slow, * n1 = NULL, * n3 = slow->next;
        while (n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3)
                n3 = n3->next;
        }
        ListNode* pcur1 = A, * pcur2 = n1;
        while (pcur2)
        {
            if (pcur1->val != pcur2->val)
                return false;
            pcur1 = pcur1->next;
            pcur2 = pcur2->next;
        }
        return true;
    }
};